package advance.day03;

import advance.day03.MaxTree.Node;

/**
 * 描述：
 *      Morris遍历,时间复杂度On，空间复杂度O1
 * @author hl
 * @version 1.0
 * @date 2020/11/6 16:38
 */
public class MorrisTraverse {

    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.right.left = new Node(5);
        head.right.right = new Node(6);
        head.left.left.right = new Node(7);
//        morrisIn(head);
        morrisPost(head);
    }

    public static void morrisIn(Node head){
        if (head == null) {
            return ;
        }
        Node cur = head;
        while(cur != null){
            Node mostRight = cur.left;
            if (mostRight != null) {
                /**
                 * 这里有两种情况：
                 * 1）mostRight.right==null表示第一次来到cur
                 * 2）mostRight.right==cur表示是第二次来到cur
                 */
                while(mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }
                //第一次来到cur
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else{//第二次来到cur
                    mostRight.right = null;
                }
            }
            //打印行为放在第二次来到cur的时候，就是中序遍历
            System.out.print(cur.value + " ");
            cur = cur.right;
        }
    }

    public static void morrisPre(Node head){
        if (head == null) {
            return ;
        }
        Node cur = head;
        while(cur != null){
            Node mostRight = cur.left;
            if (mostRight != null) {
                /**
                 * 这里有两种情况：
                 * 1）mostRight.right==null表示第一次来到cur
                 * 2）mostRight.right==cur表示是第二次来到cur
                 */
                while(mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {//第一次来到cur
                    System.out.print(cur.value + " ");//打印行为放在第一次来到cur的时候，就是先序遍历
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else{//第二次来到cur
                    mostRight.right = null;
                }
            }
            cur = cur.right;
        }
    }

    /**
     * 后序遍历：
     *      只关心可以到达两次的结点，在第二次到达的时候逆序打印左子树的有边界
     *      最后打印整棵树的有边界
     * @param head
     */
    public static void morrisPost(Node head){
        if(head == null){
            return ;
        }
        Node cur = head;
        while(cur != null){
            Node mostRight = cur.left;
            if (mostRight != null) {
                while(mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                        mostRight.right = cur;
                        cur = cur.left;
                        continue;
                }else{
                    mostRight.right = null;
                    reversionPrint(cur.left);
                }
            }
            cur = cur.right;
        }
        reversionPrint(head);
    }
    public static void reversionPrint(Node head){
        if (head == null) {
            return;
        }
        Node node = reversion(head);
        printNode(node);
        reversion(node);
    }
    public static Node reversion(Node head){
        if (head == null) {
            return null;
        }
        Node cur = head;
        Node pre = null;
        Node next;
        while(cur != null){
            next = cur.right;
            cur.right = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    public static void printNode(Node head){
        Node cur = head;
        while(cur != null){
            System.out.print(cur.value + " ");
            cur = cur.right;
        }
    }
}
